package com.ycy.leetcode.tree;

import com.google.common.collect.Lists;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BSTCengXu2 {

  TreeNode root;

  @Before
  public void before() {
    /*
       1000
    /       \
    500      2000
    /   \     /   \
    200 600 1500  2500
     */

    this.root = new TreeNode(1000);
    this.root.left = new TreeNode(500);
    this.root.right = new TreeNode(2000);

    this.root.left.left = new TreeNode(200);
    this.root.left.right = new TreeNode(600);

    this.root.right.left = new TreeNode(1500);
    this.root.right.right = new TreeNode(2500);

  }

  @Test
  public void test1() {
    preOrderBianli(this.root, 0);

    for (List<Integer> cengxuList : this.cengxuLists) {
      for (Integer integer : cengxuList) {
        System.out.print(integer + "\t");
      }
      System.out.println();
    }

  }

  List<List<Integer>> cengxuLists = Lists.newArrayList();

  /**
   * i = 0 代表第一层
   */
  public void preOrderBianli(TreeNode treeNode, int i) {
    if (treeNode == null) return;

    List<Integer> integers;
    if (i + 1 > cengxuLists.size()) {
      integers = new ArrayList<>();
      this.cengxuLists.add(integers);
    } else {
      integers = this.cengxuLists.get(i);
    }
    integers.add(treeNode.val);
    ++i;
//    System.out.println(treeNode.val);
    preOrderBianli(treeNode.left, i);
    preOrderBianli(treeNode.right, i);

  }

  @Test
  public void test() {

    queueBianli(this.root);

  }

  Queue<TreeNode> queue = new LinkedList<>();

  public void queueBianli(TreeNode treeNode) {

    int size = 1;
    queue.offer(treeNode);
    while (!queue.isEmpty()) {
      int size1 = queue.size();
      for (int i = 0; i < size1; i++) {
        TreeNode poll = queue.poll();
        System.out.print(poll.val + "\t");

        if (poll.left != null) this.queue.add(poll.left);
        if (poll.right != null) this.queue.add(poll.right);


      }
      System.out.println();
    }

  }

  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
      this.val = val;
    }
  }

}
